package gold.digger;

import java.util.Arrays;

/**
 * Created by fanzhenyu02 on 2020/3/1.
 */
public class LC31 {

    public void nextPermutation(int[] nums) {
        if (null == nums || nums.length <= 1) {
            return;
        }

        long curVal = arrToValue(nums);
        int len = nums.length;

        long swVal = arrToValue(swapPos(nums, len - 1, len - 2));
        if (curVal < swVal) {
            return;
        }

        //length equals 2
        if (len == 2) {
            return;
        }

        int start = len - 3;
        int minHeadVal = Integer.MAX_VALUE;
        int minHeadIndex = -1;
        while (start >= 0) {
            for (int k = start + 1; k < len; ++k) {
                if (nums[k] > nums[start] && nums[k] < minHeadVal) {
                    minHeadVal = nums[k];
                    minHeadIndex = k;
                }
            }

            if (minHeadIndex == -1) {
                --start;
                continue;
            }

            swapPos(nums, minHeadIndex, start);
            // do sort with index
            Arrays.sort(nums, start + 1, len);
            return;
        }

        //still didn't find valida answer,do sort from start;
        if (minHeadIndex == -1) {
            Arrays.sort(nums);
            return;
        }
    }


    public int[] swapPos(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        return arr;
    }

    public long arrToValue(int[] arr) {
        long sum = 0;
        for (int i = 0; i < arr.length; ++i) {
            sum *= 10;
            sum += arr[i];
        }

        return sum;
    }


    public static void main(String[] args) {
        LC31 an = new LC31();
        int arr[] = {2, 4, 3,1};
//        Arrays.sort(arr, 2,4);
        an.nextPermutation(arr);

//        System.out.println(Integer.MIN_VALUE);
    }
}
